# 请判断一个链表是否为回文链表。 
# 
#  示例 1: 
# 
#  输入: 1->2
# 输出: false 
# 
#  示例 2: 
# 
#  输入: 1->2->2->1
# 输出: true
#  
# 
#  进阶： 
# 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
#  Related Topics 链表 双指针 
#  👍 956 👎 0


from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def isPalindrome(self, head: ListNode) -> bool:
        half_end = self.half_end(head)
        reverse = self.reverse_list(half_end.next)
        first, second = head, reverse
        while first and second:
            if first.val != second.val:
                return False
            first = first.next
            second = second.next
        second_start = self.reverse_list(second)
        half_end.next = second_start
        return True


    def half_end(self, head):
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverse_list(self, head):
        prev, curr = None, head
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# vals[::-1] 切片, 从尾切到头, 步进为1
# 解法1: 将链表存入数组, 分别从头和从尾比较值
#     def isPalindrome(self, head: ListNode) -> bool:
#         vals = []
#         while head:
#             vals.append(head.val)
#             head = head.next
#         return vals == vals[::-1]

# 解法2: 递归
# 外侧节点指向头, 利用递归栈走到尾, 比较头尾, 不断向中间逼近
# 使用堆栈开销较大
# 1->2->2->1
#
#     def __init__(self):
#         self.front = None
#
#     def isPalindrome(self, head: ListNode) -> bool:
#         self.front = head
#
#         def rec_check(current):
#             if current is not None:
#                 if not rec_check(current.next):
#                     return False
#                 if self.front.val != current.val:
#                     return False
#                 self.front = self.front.next
#             return True
#
#         return rec_check(head)

"""
1->2->2->1
1
    2
        2
            1
"""
"""
3. 快慢指针, 将链表分成两部分, 翻转后一部分, 然后比较
1-2-3
"""
#
# def isPalindrome(self, head: ListNode) -> bool:
#     if head is None:
#         return True
#     first_half_end = self.end_of_first_half(head)
#     reverse_start = self.reverse_list(first_half_end.next)
#     first_position = head
#     second_position = reverse_start
#     while first_position and second_position:
#         if first_position.val != second_position.val:
#             return False
#         first_position = first_position.next
#         second_position = second_position.next
#     second_half_start = self.reverse_list(reverse_start)
#     first_half_end.next = second_half_start
#     return True
#
# def end_of_first_half(self, head):
#     slow = head
#     fast = head
#     while fast.next and fast.next.next:
#         slow = slow.next
#         fast = fast.next.next
#     return slow
#
# def reverse_list(self, head):
#     prev = None
#     current = head
#     while current:
#         next = current.next
#         current.next = prev
#         prev = current
#         current = next
#     return prev

if __name__ == '__main__':
    s = Solution()
    # 1->2->2->1
    h = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
    assert s.isPalindrome(h)
    # 1->2->3
    h1 = ListNode(1, ListNode(2))
    assert not s.isPalindrome(h1)
    h2 = ListNode(1)
    assert s.isPalindrome(h2)
